package com.tucc.hello.leetcode.no1_400.no1_200.no21_40.no37;

import cn.hutool.json.JSONUtil;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] board = solution.readData(TEST_DATA);
        solution.solveSudoku(board);
        solution.printBoard(board);
    }

    public static final int SIZE = 9;
    boolean isSolve = false;
    public static final char[] chars = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};

    public void solveSudoku(char[][] board) {
        trySolve(board, 0);
    }

    private void trySolve(char[][] board, int k) {
//        System.out.println(k);
        int i = 0, j = 0;
        while (k < SIZE * SIZE) {
            i = k / SIZE;
            j = k % SIZE;
            if (board[i][j] == '.') {
                break;
            }
            k++;
        }
        if (k < SIZE * SIZE) {
            for (int c = 1; c <= SIZE; c++) {
                if (!isConflict(board, i, j, chars[c])) {
                    board[i][j] = chars[c];
//                    printBoard(board);
                    trySolve(board, k + 1);
                    if (isAllSolve(board)) {
                        return;
                    } else {
                        board[i][j] = '.';
                    }
                }
            }
        }
    }

    private boolean isAllSolve(char[][] board) {
        if (isSolve) {
            return true;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char ch = board[i][j];
                if (ch == '.') {
                    return false;
                }
            }
        }
        isSolve = true;
        return true;
    }

    private boolean isConflict(char[][] board, int i, int j, char ch) {
        for (int a = 0; a < SIZE; a++) {
            if (board[i][a] == ch || board[a][j] == ch) {
                return true;
            }
        }
        int lineSt = i / 3 * 3;
        int columnSt = j / 3 * 3;
//        System.out.println(String.format("%d %d block:%d %d", i, j, lineSt, columnSt));
        for (int a = lineSt; a < lineSt + 3; a++) {
            for (int b = columnSt; b < columnSt + 3; b++) {
                if (board[a][b] == ch) {
                    return true;
                }
            }
        }
        return false;
    }

    public char[][] readData(String data) {
        List<String> stringList = JSONUtil.toList(data, String.class);
        char[][] chars = new char[stringList.size()][];
        for (int i = 0; i < chars.length; i++) {
            String string = stringList.get(i);
            string = string.substring(1, string.length() - 1).replaceAll("[\",]", "");
            chars[i] = string.toCharArray();
        }
        return chars;
    }


    private void printBoard(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                char ch = board[i][j];
                System.out.print(ch);
            }
            System.out.println();
        }
    }

    public static final String TEST_DATA2 =
            "[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]," +
                    "[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]," +
                    "[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]," +
                    "[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]," +
                    "[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]," +
                    "[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]," +
                    "[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]," +
                    "[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]," +
                    "[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]";


    public static final String TEST_DATA = "[[\".\",\".\",\"9\",\"7\",\"4\",\"8\",\".\",\".\",\".\"],[\"7\",\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\"],[\".\",\"2\",\".\",\"1\",\".\",\"9\",\".\",\".\",\".\"],[\".\",\".\",\"7\",\".\",\".\",\".\",\"2\",\"4\",\".\"],[\".\",\"6\",\"4\",\".\",\"1\",\".\",\"5\",\"9\",\".\"],[\".\",\"9\",\"8\",\".\",\".\",\".\",\"3\",\".\",\".\"],[\".\",\".\",\".\",\"8\",\".\",\"3\",\".\",\"2\",\".\"],[\".\",\".\",\".\",\".\",\".\",\".\",\".\",\".\",\"6\"],[\".\",\".\",\".\",\"2\",\"7\",\"5\",\"9\",\".\",\".\"]]";
}
